|
In elementary set theory, Cantor's theorem states that, for any set ''A'', the set of all subsets of ''A'' (the power set of ''A'') has a strictly greater cardinality than ''A'' itself. For finite sets, Cantor's theorem can be seen to be true by a much simpler proof than that given below. Counting the empty subset, subsets of ''A'' with just one member, etc. for a set with members there are subsets and the cardinality of the set of subsets is clearly larger. But the theorem is true of infinite sets as well. In particular, the power set of a countably infinite set is uncountably infinite. The theorem is named for German mathematician Georg Cantor, who first stated and proved it. ==Proof== Two sets are equinumerous (have the same cardinality) if and only if there exists a bijection (a one-to-one correspondence) between them. To establish Cantor's theorem it is enough to show that, for any given set ''A'', no function ''f'' from ''A'' into the power set of ''A'', can be surjective, i.e. to show the existence of at least one subset of ''A'' that is not an element of the image of ''A'' under ''f''. Such a subset is given by the following construction, sometimes called the ''Cantor diagonal set'' of ''f'': : This means, by definition, that for all ''x'' in ''A'', ''x'' ∈ ''B'' if and only if ''x'' ∉ ''f''(''x''). For all ''x'' the sets ''B'' and ''f''(''x'') cannot be the same because ''B'' was constructed from elements of ''A'' whose images (under ''f'') did not include themselves. More specifically, consider any ''x'' ∈ ''A'', then either ''x'' ∈ ''f''(''x'') or ''x'' ∉ ''f''(''x''). In the former case, ''f''(''x'') cannot equal ''B'' because ''x'' ∈ ''f''(''x'') by assumption and ''x'' ∉ ''B'' by the construction of ''B''. In the latter case, ''f''(''x'') cannot equal ''B'' because ''x'' ∉ ''f''(''x'') by assumption and ''x'' ∈ ''B'' by the construction of ''B''. Slightly more formally, we just proved that the assumption that there exists ''x'' in ''A'' such that ''f''(''x'') = ''B'' implies the contradiction: : Therefore, by reductio ad absurdum, the assumption must be false.〔 Thus there is no ''x'' such that ''f''(''x'') = ''B''; in other words, ''B'' is not in the image of ''f''. Because ''B'' is in the power set of ''A'', the power set of ''A'' has a greater cardinality than ''A'' itself. Another way to think of the proof is that ''B'', empty or non-empty, is always in the power set of ''A''. For ''f'' to be onto, some element of ''A'' must map to ''B''. But that leads to a contradiction: no element of ''B'' can map to ''B'' because that would contradict the criterion of membership in ''B'', thus the element mapping to ''B'' must not be an element of ''B'' meaning that it satisfies the criterion for membership in ''B'', another contradiction. So the assumption that an element of ''A'' maps to ''B'' must be false; and ''f'' can not be onto. Because of the double occurrence of ''x'' in the expression "''x'' ∉ ''f''(''x'')", this is a diagonal argument. For a countable (or finite) set, the argument of the proof given above can be illustrated by constructing a table in which each row is labelled by a unique ''x'' from ''A'' = , in this order. ''A'' is assumed to admit a linear order so that such table can be constructed. Each column of the table is labelled by a unique ''y'' from the power set of ''A''; the columns are ordered by the argument to ''f'', i.e. the column labels are ''f''(''x''1), ''f''(''x''2), ..., in this order. The intersection of each row ''x'' and column ''y'' records a true/false bit whether ''x'' ∈ ''y''. Given the order chosen for the row and column labels, the main diagonal ''D'' of this table thus records whether ''x'' ∈ ''f''(''x'') for all ''x'' in ''A''. The set ''B'' constructed in the previous paragraphs coincides with the row labels for the subset of entries on this main diagonal ''D'' where the table records that ''x'' ∈ ''f''(''x'') is false.〔〕 Each column records the values of the indicator function of the set corresponding to the column. The indicator function of ''B'' coincides with of the logically negated (true ↔ false) entries of the main diagonal. Thus the indicator function of ''B'' does not agree with any column in at least one entry. Consequently, no column represents ''B''. For a finite set, the proof can also be illustrated using a more prosaic presentation known as the barber paradox. Despite the simplicity of the above proof, it is rather difficult for an automated theorem prover to produce it. The main difficulty lies in an automated discovery of the Cantor diagonal set. Lawrence Paulson noted in 1992 that Otter could not do it, whereas Isabelle could, albeit with a certain amount of direction in terms of tactics that might perhaps be considered cheating.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Cantor's theorem」の詳細全文を読む スポンサード リンク
|